package com.demo.java.OD251_300.OD253;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【无向图染色问题 or 红黑图】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146029254
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 读取节点数和边数
        int numVertices = sc.nextInt();
        int numEdges = sc.nextInt();

        // 节点数为负或0时直接返回0
        if (numVertices <= 0) {
            System.out.println(0);
            return;
        }

        // 最大可能的边数为 n*(n-1)/2
        int maxEdges = numVertices * (numVertices - 1) / 2;

        // 如果边数小于等于0或超过最大边数，直接输出2^n
        if (numEdges <= 0 || numEdges > maxEdges) {
            System.out.println(1 << numVertices);
            return;
        }

        // 构建图的边
        List<int[]> edgeList = new ArrayList<>();
        for (int i = 0; i < numEdges; i++) {
            edgeList.add(new int[]{sc.nextInt(), sc.nextInt()});
        }

        // 所有可能的节点组合数量为2^n
        int total = 1 << numVertices;
        int res = total;

        // 使用位图表示节点的颜色状态
        BitSet vertexSubset = new BitSet(numVertices);

        // 遍历所有可能的节点染色组合
        for (int i = 0; i < total; i++) {
            vertexSubset.clear();
            int temp = i;

            // 根据当前的二进制数设置每个节点的颜色
            for (int j = 0; j < numVertices; j++) {
                if ((temp & 1) == 1) {
                    vertexSubset.set(j);
                }
                temp >>= 1;
            }

            // 检查每条边的染色是否符合要求
            for (int[] edge : edgeList) {
                // 如果这条边的两个端点颜色相同，则不符合二分图要求
                if (!vertexSubset.get(edge[0]) && !vertexSubset.get(edge[1])) {
                    res--;
                    break;
                }
            }
        }

        // 输出符合要求的染色方案数
        System.out.println(res);
    }
}